# -*- coding: utf-8 -*-

# 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素

# 示例 1:
# 输入:
# [
#  [ 1, 2, 3 ],
#  [ 4, 5, 6 ],
#  [ 7, 8, 9 ]
# ]
# 输出: [1,2,3,6,9,8,7,4,5]

# 示例 2:
# 输入:
# [
#   [1, 2, 3, 4],
#   [5, 6, 7, 8],
#   [9,10,11,12]
# ]
# 输出: [1,2,3,4,8,12,11,10,9,5,6,7]








# 解题思路：
# 总体思路是一层一层的顺时针输出
# eg:
# 1  2  3  4
# 5  6  7  8
# 9  10 11 12
# 
# 1、
# @  @  @  @
# 1  2  3  4
# 5  6  7  8
# 9  10 11 12
# 
# 2、
# @  @  @  @   
# 1  2  3  4   
# 5  6  7  8  @
# 9  10 11 12 @
# 
# 3、
# @  @  @  @   
# 1  2  3  4  
# 5  6  7  8  @
# 9  10 11 12 @
# @  @  @      

# 4、
#   @  @  @  @   
#   1  2  3  4  
# @ 5  6  7  8  @
#   9  10 11 12 @
#   @  @  @      

# 通过观察 顺时针螺旋输出是依下面的方向进行
# 并且每次在方向上行走的步骤也是有规律的
# 右   下   左   上   右   下   左   上...
# R   C-1  R-1  C-2  R-2  C-3 R-3..C-4...
# 依此规律完成下面的代码
class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        rtn = [];

        if not matrix:
            return rtn;

        matrix_row = len(matrix);
        matrix_col = len(matrix[0]);

        row = 0;
        col = -1;
        step = 0;

        while step // 2 < matrix_row and step // 2 < matrix_col:
            step += 1;

            direction = matrix_col;
            if step % 2 == 0:
                direction = matrix_row;

            for i in range(direction - step // 2):
                if step %4 == 0:
                    row -= 1;
                elif step % 4 == 1:
                    col += 1;
                elif step % 4 == 2:
                    row += 1;
                elif step % 4 == 3:
                    col -= 1;
                rtn.append(matrix[row][col]);

            print rtn;
        return rtn;




# 阅读官方解题方案
# 更容易理解，更容易记忆
# 解题思路 顺时针移动 遇到边界或者已经访问过的位置更改方向
# 相对于上面的解决方案，没有了复杂的 每一步 行走长度的推演
# 更加直观的方向表示方式
class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        rtn = [];

        if not matrix:
            return rtn;

        row = len(matrix);
        col = len(matrix[0]);

        seen = [ [False] * col for _ in range(row) ];
        direction = [ [0,1], [1,0], [0,-1], [-1,0] ];

        r = 0;
        c = 0;
        di = 0;

        for _ in range(row * col):
            seen[r][c] = True;
            rtn.append(matrix[r][c]);

            next_r, next_c = r + direction[di][0], c + direction[di][1];
            if 0 <= next_r < row and 0 <= next_c < col and not seen[next_r][next_c]:
                r = next_r;
                c = next_c;
            else:
                di = (di + 1) % 4;
                r, c = r + direction[di][0], c + direction[di][1];

        return rtn;


t = Solution();
# print t.spiralOrder([[1,2,3],[4,5,6],[7,8,9]]);
print t.spiralOrder([[1,2,3,4],[5,6,7,8],[9,10,11,12]]);
